package com.yanceysong.codetop.s91_s100;

import java.util.Deque;
import java.util.LinkedList;

public class S92_Mid_227_基本计算器_II {
    /**
     * .S92_Mid_227_基本计算器 II
     * .<p>
     * .<a href="https://leetcode.cn/problems/basic-calculator-ii/">...</a>
     * .<p>
     * .给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
     * .<p>
     * .整数除法仅保留整数部分。
     * .<p>
     * .你可以假设给定的表达式总是有效的。所有中间结果将在 [-2^31, 2^31 - 1] 的范围内。
     * .<p>
     * .注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
     * .<p>
     * .示例：
     * .<p>
     * .输入：s = "3+2*2"
     * .输出：7
     * .<p>
     * .输入：s = " 3/2 "
     * .输出：1
     * .<p>
     * .输入：s = " 3+5 / 2 "
     * .输出：5
     * .<p>
     * .提示：
     * .<p>
     * .1 <= s.length <= 3 * .10^5
     * .s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
     * .s 表示一个有效的表达式
     * .表达式中的所有整数都是非负整数，且在范围 [0, 2^31 - 1] 内
     * .题目数据保证答案是一个 32-bit 整数
     * .<p>
     * .核心标签：栈、字符串、数学
     * .<p>
     * .使用栈来处理运算符优先级问题
     * .<p>
     * .算法原理：
     * .- 由于乘除法优先级高于加减法，需要先处理乘除法
     * .- 使用栈来保存待相加的数字
     * .- 遇到加法：直接将数字入栈
     * .- 遇到减法：将数字的负数入栈
     * .- 遇到乘法：弹出栈顶元素与当前数字相乘后入栈
     * .- 遇到除法：弹出栈顶元素与当前数字相除后入栈
     * .- 最后将栈中所有数字相加得到结果
     * .<p>
     * .关键洞察：
     * .1. 通过将减法转换为加负数，统一了加减法的处理
     * .2. 乘除法立即计算并更新栈顶，保证了运算符优先级
     * .3. 使用前一个运算符（preSign）来决定如何处理当前数字
     * .4. 最后一个数字需要特殊处理（i == n - 1）
     * .<p>
     * .图解示例：s = "3+2*2"
     * .<p>
     * .初始状态：
     * .stack = []
     * .preSign = '+'
     * .currentNum = 0
     * .<p>
     * .第1步：读取字符'3'
     * ."3+2*2"
     * .↑
     * .currentNum = 3
     * .<p>
     * .第2步：读取字符'+'（运算符）
     * ."3+2*2"
     * .↑
     * .根据preSign='+'，将3入栈
     * .stack = [3]
     * .preSign = '+'
     * .currentNum = 0
     * .<p>
     * .第3步：读取字符'2'
     * ."3+2*2"
     * .↑
     * .currentNum = 2
     * .<p>
     * .第4步：读取字符'*'（运算符）
     * ."3+2*2"
     * .↑
     * .根据preSign='+'，将2入栈
     * .stack = [3, 2]
     * .preSign = '*'
     * .currentNum = 0
     * .<p>
     * .第5步：读取字符'2'
     * ."3+2*2"
     * .↑
     * .currentNum = 2
     * .<p>
     * .第6步：到达字符串末尾
     * ."3+2*2"
     * .↑
     * .根据preSign='*'，弹出栈顶2，计算2*2=4，将4入栈
     * .stack = [3, 4]
     * .<p>
     * .第7步：计算栈中所有元素之和
     * .stack = [3, 4]
     * .result = 3 + 4 = 7
     * .<p>
     * .复杂示例：s = "14-3/2"
     * .<p>
     * .步骤1-2：读取"14"和"-"
     * .stack = [14], preSign = '-', currentNum = 0
     * .<p>
     * .步骤3-4：读取"3"和"/"
     * .根据preSign='-'，将-3入栈
     * .stack = [14, -3], preSign = '/', currentNum = 0
     * .<p>
     * .步骤5-6：读取"2"并到达末尾
     * .根据preSign='/'，弹出-3，计算-3/2=-1，将-1入栈
     * .stack = [14, -1]
     * .<p>
     * .步骤7：计算结果
     * .result = 14 + (-1) = 13
     * .<p>
     * .运算符优先级处理可视化：
     * .<p>
     * .表达式："3+2*2"
     * .<p>
     * .传统计算顺序（考虑优先级）：
     * .3 + (2 * .2) = 3 + 4 = 7
     * .<p>
     * .栈处理过程：
     * .1. 遇到+：将3入栈 → [3]
     * .2. 遇到*：将2入栈 → [3, 2]
     * .3. 末尾：执行2*2=4，替换栈顶 → [3, 4]
     * .4. 求和：3+4=7
     * .<p>
     * .时间复杂度：O(n)，其中n为字符串长度，需要遍历字符串一次
     * .空间复杂度：O(n)，栈中最多存储O(n)个数字（全是加法的情况）
     */
    public int calculate(String s) {
        // 使用栈来保存待相加的数字
        Deque<Integer> stack = new LinkedList<>();
        
        // 前一个运算符，初始化为'+'（假设表达式前有一个隐式的+号）
        char previousOperator = '+';
        
        // 当前正在构建的数字
        int currentNum = 0;
        
        // 字符串长度
        int length = s.length();
        
        // 遍历字符串中的每个字符
        for (int i = 0; i < length; i++) {
            char currentChar = s.charAt(i);
            
            // 如果是数字字符，构建完整的数字（处理多位数）
            if (Character.isDigit(currentChar)) {
                currentNum = currentNum * 10 + (currentChar - '0');
            }
            
            // 如果是运算符（非数字且非空格）或到达字符串末尾
            // 需要处理前一个运算符和当前数字
            if ((!Character.isDigit(currentChar) && currentChar != ' ') || i == length - 1) {
                // 根据前一个运算符决定如何处理当前数字
                switch (previousOperator) {
                    case '+':
                        // 加法：直接将数字入栈
                        stack.push(currentNum);
                        break;
                    case '-':
                        // 减法：将数字的负数入栈（转换为加法）
                        stack.push(-currentNum);
                        break;
                    case '*':
                        // 乘法：弹出栈顶元素，与当前数字相乘后入栈
                        stack.push(stack.pop() * currentNum);
                        break;
                    case '/':
                        // 除法：弹出栈顶元素，与当前数字相除后入栈
                        // Java中整数除法自动向零取整
                        stack.push(stack.pop() / currentNum);
                        break;
                }
                
                // 更新前一个运算符为当前字符
                previousOperator = currentChar;
                
                // 重置当前数字
                currentNum = 0;
            }
        }
        
        // 计算栈中所有数字的和
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }
        
        return result;
    }

    public static void main(String[] args) {
        S92_Mid_227_基本计算器_II solution = new S92_Mid_227_基本计算器_II();

        System.out.println("=== 基本计算器II测试开始 ===");

        // 测试1: 题目示例1 - "3+2*2"
        System.out.println("\n--- 测试1: \"3+2*2\" ---");
        testCase1(solution);

        // 测试2: 题目示例2 - " 3/2 "
        System.out.println("\n--- 测试2: \" 3/2 \" ---");
        testCase2(solution);

        // 测试3: 题目示例3 - " 3+5 / 2 "
        System.out.println("\n--- 测试3: \" 3+5 / 2 \" ---");
        testCase3(solution);

        // 测试4: 单个数字
        System.out.println("\n--- 测试4: 单个数字 \"42\" ---");
        testSingleNumber(solution);

        // 测试5: 简单加法
        System.out.println("\n--- 测试5: 简单加法 \"1+1\" ---");
        testSimpleAddition(solution);

        // 测试6: 简单减法
        System.out.println("\n--- 测试6: 简单减法 \"5-3\" ---");
        testSimpleSubtraction(solution);

        // 测试7: 连续乘法
        System.out.println("\n--- 测试7: 连续乘法 \"2*3*4\" ---");
        testMultipleMultiplication(solution);

        // 测试8: 混合运算
        System.out.println("\n--- 测试8: 混合运算 \"14-3/2\" ---");
        testMixedOperations(solution);

        // 测试9: 复杂表达式
        System.out.println("\n--- 测试9: 复杂表达式 \"1*2-3/4+5*6-7*8+9/10\" ---");
        testComplexExpression(solution);

        // 测试10: 带空格的表达式
        System.out.println("\n--- 测试10: 带空格 \"  10  +  20  * . 3  \" ---");
        testWithSpaces(solution);

        // 测试11: 多位数
        System.out.println("\n--- 测试11: 多位数 \"100+200*3\" ---");
        testMultiDigitNumbers(solution);

        // 测试12: 除法向零取整
        System.out.println("\n--- 测试12: 除法向零取整 \"7/3\" ---");
        testDivisionTruncation(solution);

        // 测试13: 负数结果
        System.out.println("\n--- 测试13: 负数结果 \"1-5\" ---");
        testNegativeResult(solution);

        // 测试14: 全是加法
        System.out.println("\n--- 测试14: 全是加法 \"1+2+3+4+5\" ---");
        testAllAddition(solution);

        // 测试15: 优先级测试
        System.out.println("\n--- 测试15: 优先级 \"2+3*4-5/2\" ---");
        testOperatorPrecedence(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试用例1: "3+2*2"
     * .计算过程：3 + (2*2) = 3 + 4 = 7
     */
    private static void testCase1(S92_Mid_227_基本计算器_II solution) {
        String s = "3+2*2";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 7)");
        assert result == 7 : "结果应该是7";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试用例2: " 3/2 "
     * .计算过程：3/2 = 1（整数除法）
     */
    private static void testCase2(S92_Mid_227_基本计算器_II solution) {
        String s = " 3/2 ";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 1)");
        assert result == 1 : "结果应该是1";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试用例3: " 3+5 / 2 "
     * .计算过程：3 + (5/2) = 3 + 2 = 5
     */
    private static void testCase3(S92_Mid_227_基本计算器_II solution) {
        String s = " 3+5 / 2 ";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 5)");
        assert result == 5 : "结果应该是5";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试用例4: 单个数字 "42"
     */
    private static void testSingleNumber(S92_Mid_227_基本计算器_II solution) {
        String s = "42";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 42)");
        assert result == 42 : "结果应该是42";
        System.out.println("✓ 单个数字测试通过");
    }

    /**
     * .测试用例5: 简单加法 "1+1"
     */
    private static void testSimpleAddition(S92_Mid_227_基本计算器_II solution) {
        String s = "1+1";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 2)");
        assert result == 2 : "结果应该是2";
        System.out.println("✓ 简单加法测试通过");
    }

    /**
     * .测试用例6: 简单减法 "5-3"
     */
    private static void testSimpleSubtraction(S92_Mid_227_基本计算器_II solution) {
        String s = "5-3";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 2)");
        assert result == 2 : "结果应该是2";
        System.out.println("✓ 简单减法测试通过");
    }

    /**
     * .测试用例7: 连续乘法 "2*3*4"
     * .计算过程：(2*3)*4 = 6*4 = 24
     */
    private static void testMultipleMultiplication(S92_Mid_227_基本计算器_II solution) {
        String s = "2*3*4";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 24)");
        assert result == 24 : "结果应该是24";
        System.out.println("✓ 连续乘法测试通过");
    }

    /**
     * .测试用例8: 混合运算 "14-3/2"
     * .计算过程：14 - (3/2) = 14 - 1 = 13
     */
    private static void testMixedOperations(S92_Mid_227_基本计算器_II solution) {
        String s = "14-3/2";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 13)");
        assert result == 13 : "结果应该是13";
        System.out.println("✓ 混合运算测试通过");
    }

    /**
     * .测试用例9: 复杂表达式 "1*2-3/4+5*6-7*8+9/10"
     * .计算过程：2 - 0 + 30 - 56 + 0 = -24
     */
    private static void testComplexExpression(S92_Mid_227_基本计算器_II solution) {
        String s = "1*2-3/4+5*6-7*8+9/10";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: -24)");
        assert result == -24 : "结果应该是-24";
        System.out.println("✓ 复杂表达式测试通过");
    }

    /**
     * .测试用例10: 带空格的表达式 "  10  +  20  * . 3  "
     * .计算过程：10 + (20*3) = 10 + 60 = 70
     */
    private static void testWithSpaces(S92_Mid_227_基本计算器_II solution) {
        String s = "  10  +  20  * . 3  ";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 70)");
        assert result == 70 : "结果应该是70";
        System.out.println("✓ 带空格测试通过");
    }

    /**
     * .测试用例11: 多位数 "100+200*3"
     * .计算过程：100 + (200*3) = 100 + 600 = 700
     */
    private static void testMultiDigitNumbers(S92_Mid_227_基本计算器_II solution) {
        String s = "100+200*3";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 700)");
        assert result == 700 : "结果应该是700";
        System.out.println("✓ 多位数测试通过");
    }

    /**
     * .测试用例12: 除法向零取整 "7/3"
     * .计算过程：7/3 = 2（向零取整）
     */
    private static void testDivisionTruncation(S92_Mid_227_基本计算器_II solution) {
        String s = "7/3";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 2)");
        assert result == 2 : "结果应该是2";
        System.out.println("✓ 除法向零取整测试通过");
    }

    /**
     * .测试用例13: 负数结果 "1-5"
     * .计算过程：1 - 5 = -4
     */
    private static void testNegativeResult(S92_Mid_227_基本计算器_II solution) {
        String s = "1-5";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: -4)");
        assert result == -4 : "结果应该是-4";
        System.out.println("✓ 负数结果测试通过");
    }

    /**
     * .测试用例14: 全是加法 "1+2+3+4+5"
     * .计算过程：1+2+3+4+5 = 15
     */
    private static void testAllAddition(S92_Mid_227_基本计算器_II solution) {
        String s = "1+2+3+4+5";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 15)");
        assert result == 15 : "结果应该是15";
        System.out.println("✓ 全是加法测试通过");
    }

    /**
     * .测试用例15: 优先级测试 "2+3*4-5/2"
     * .计算过程：2 + (3*4) - (5/2) = 2 + 12 - 2 = 12
     */
    private static void testOperatorPrecedence(S92_Mid_227_基本计算器_II solution) {
        String s = "2+3*4-5/2";
        System.out.println("输入表达式: \"" + s + "\"");
        int result = solution.calculate(s);
        System.out.println("calculate() -> " + result + " (期望: 12)");
        assert result == 12 : "结果应该是12";
        System.out.println("✓ 优先级测试通过");
    }
}

